import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: Map和Set练习题
 */
public class Test2 {

    /**
     * 前 k 个高频单词
     * @param words 单词
     * @param k 要求个数
     * @return
     */
    public List<String> topKFrequent(String[] words, int k) {
        if(words.length == 0 || k == 0) {
            return null;
        }
        //1. 用HashMap保存单词和次数
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++) {
            if(map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            }else {
                map.put(words[i], 1);
            }
        }
        //2. 创建大小为K的小根堆，（传比较器，先比较次数，次数相等比较字符串字典序）
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> e1,Map.Entry<String, Integer> e2) {
                return e1.getValue().equals(e2.getValue()) ?
                        e1.getValue().compareTo(e2.getValue()) :
                        e2.getKey().compareTo(e1.getKey());
            }
        });

        //3.遍历整个数组得到最大的前 k 个值
        //需要利用for-each方法，就要先调用Map.entrySet()方法
        Set<Map.Entry<String, Integer>> set = map.entrySet();
        int i = 0;
        for(Map.Entry<String, Integer> e : set) {
            if(i < k) {
                queue.offer(e);
            }else {
                if(queue.peek().getValue().compareTo(e.getValue()) < 0) {
                    queue.poll();
                    queue.offer(e);
                }else if(queue.peek().getValue().equals(e.getValue())){
                    //字典序小的入堆
                    if(queue.peek().getKey().compareTo(e.getKey()) > 0) {
                        queue.poll();
                        queue.offer(e);
                    }
                }
            }
            i++;
        }
        //list保存前 k 个次数最多的单词
        List<String> list = new ArrayList<>();
        while(!queue.isEmpty()) {
            list.add(queue.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    //旧键盘，找出缺失按键
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();
            s1 = s1.toUpperCase();
            s2 = s2.toUpperCase();
            Set<Character> set = new HashSet<>();
            for(int i = 0; i < s2.length(); i++) {
                set.add(s2.charAt(i));
            }
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < s1.length(); i++) {
                if(!set.contains(s1.charAt(i))) {
                    sb.append(s1.charAt(i));
                    set.add(s1.charAt(i));
                }
            }
            System.out.println(sb.toString());
        }
    }

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        if(jewels == null || stones == null) {
            return 0;
        }
        Set<Character> set = new HashSet<>();
        for(int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        int count = 0;
        for(int i = 0; i < stones.length(); i++) {
            if(set.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 复制带随机指针的链表（深度拷贝）
     * @param head  被复制的链表头节点
     * @return 复制之后新链表的头节点
     */
    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        //创建HashMap
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        Node node = null;
        //将对应的节点两两对应插入到Map中
        //并将val和next的值进行赋值
        while(cur != null) {
            Node nodeNext = new Node(cur.val);
            if(node != null) {
                node.next = nodeNext;
            }
            map.put(cur,nodeNext);
            node = nodeNext;
            cur = cur.next;
        }
        //遍历HashMap,找到key节点的random的键值对
        //然后将val的节点的random的值赋值为
        //(找到的key的节点的rando节点的键值对的val值)
        cur = head;
        while(cur != null) {
            Node randomNode = cur.random;
            Node curValNode = map.get(cur);
            if(randomNode != null) {
                Node randomValNode = map.get(randomNode);
                curValNode.random = randomValNode;
            }
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 只出现一次的数字，其余数字都出现两次
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            }else {
                set.remove(nums[i]);
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return 0;
    }
}
